use std::fmt::Display;
///二叉树

//节点 PartialOrd：可比较
struct Node<K, V> where K: Display + PartialOrd, V: Display {
    left: Option<Box<Node<K,V>>>,
    right: Option<Box<Node<K,V>>>,
    key: K,
    value: V,
    deep: u8,
}

impl <K, V> Node<K, V> where K: Display + PartialOrd, V: Display {
    fn new(key: K, value: V, deep: u8) -> Node<K, V> {
        Node {
            left: None,
            right: None,
            key,
            value,
            deep
        }
    }
    fn insert(&mut self, key: K, value: V) {
        if self.key < key {
            if let Some(ref mut right) = self.right {
                right.insert(key, value); //递归
            }else {
                self.right = Some(Box::new(Node::new(key, value, self.deep + 1)));
            }
        }else {
            if let Some(ref mut left) = self.left {
                left.insert(key, value); //递归
            }else {
                self.left = Some(Box::new(Node::new(key, value, self.deep + 1)));
            }
        }
    }
    //先序遍历
    fn show(&self) {
        for i in 0..self.deep - 1 {
            print!("-")
        }
        print!("{}",format!("key={}, value={}", self.key, self.value));
        println!();
        match self.left {
            Some(ref node) =>{
                node.show();
            },
            None =>{}
        }
        match self.right {
            Some(ref node) =>{
                node.show();
            },
            None =>{}
        }
    }
}
//二叉树
struct BinaryTree <K, V> where K: Display + PartialOrd, V: Display {
    root: Option<Box<Node<K, V>>>,
    size: u32,
}

impl<K, V> BinaryTree<K, V> where K: Display + PartialOrd, V: Display {
    fn new() -> BinaryTree<K, V> {
        BinaryTree {
            root: None,
            size: 0,
        }
    }
    //插入节点
    fn insert(&mut self, key: K, value: V) {
        if let Some(ref mut r) = self.root {
            r.insert(key, value);
        }else {
            self.root = Some(Box::new(Node::new(key, value, 1)));
        }
        self.size += 1;
    }
    //遍历
    fn show(&self) {
        match self.root {
            Some(ref node) =>{
                node.show();
            },
            None => {}
        }
    }
}

pub fn binary_tree_demo(){
    let mut tree = BinaryTree::new();
    tree.insert(3, "hello");
    tree.insert(2, "hello");
    tree.insert(4, "hello");
    tree.insert(6, "hello");
    tree.insert(1, "hello");
    tree.insert(5, "hello");
    tree.show();
}
